#pragma once
#include <iostream>
using namespace std;
#include <vector>

namespace open_adress
{
    template <class K, class V>
    class HashData
    {
    public:
        enum State
        {
            EMPTY,
            EXIST,
            DELETE
        };

    public:
        pair<K, V> _kv;
        State _state;
    };

    template <class K, class V>
    class HashTable
    {
    public:
        bool insert(const pair<K, V> &kv)
        {
            /*使用开放定址法：
            会不会找不到合适的位置， 不会。因为有负载因子。
            哈希表要判断负载因子， 负载因子越大，哈希冲突越多， 效率越低。
            负载因子越小， 哈希冲突越小， 效率越高， 但是会占用大量空间。*/

            if (_tables.size() == 0 || (_n * 10) / _tables.size() >= 7)
            {
                /*超过了负载因子， 那么就要扩容了。*/
                UpMemory();
            }
            if (Find(kv.first))
                return false;
            /*插入主逻辑*/
            int hashi = kv.first % _tables.size();
            while (_tables[hashi]._state == HashData<K, V>::State::EXIST)
            {
                hashi++;
                hashi %= _tables.size();
            }

            _tables[hashi]._kv = kv;
            _tables[hashi]._state = HashData<K, V>::State::EXIST;
            _n++;
        }

        HashData<K, V> *Find(const K &key) /*查找， 如果找到了，就返回对应的地址， 如果没找到， 就返回nullptr*/
        {
            /*这里不用循环遍历找？ 直接hashi， 直到hashi对应的值是key*/
            int hashi = key % _tables.size(); /*先映射，这个位置应该是原本应该在的位置， 但是可能被别人占用了， 这个
                                               时候就要向后遍历， 只要一发现， 这个位置不是空的，DELETE也算，
                                               因为DELETE说明这个位置之前有数据， 不知道这个数据在元数据之前是否
                                               插入的。  就要继续向后找。*/
            int tmp = hashi;
            while (_tables[hashi]._state != HashData<K, V>::EMPTY)
            {
                if (_tables[hashi]._state == HashData<K, V>::EXIST && _tables[hashi]._kv.first == key)
                {
                    return &_tables[hashi];
                }
                hashi++;
                hashi %= _tables.size();
                if (hashi == tmp)
                    return nullptr;
            }

            return nullptr;
        }

        bool Erase(const K &key) /*删除操作， 查找到对应的地址， 然后就将对应的地址位置变成Delete*/
        {
            HashData<K, V> *pdata = Find(key);
            if (pdata == nullptr)
                return false; /*找到了， 不是空， 那么久false*/
            pdata->_state = HashData<K, V>::DELETE;
            --_n;
            return true;
        }

        void Order()
        {
            cout << _n << endl;
            for (int i = 0; i < _tables.size(); i++)
            {
                if (_tables[i]._state == HashData<K, V>::EXIST)
                    cout << _tables[i]._kv.first << " : " << _tables[i]._kv.second << endl;
            }
        }

    private:
        void UpMemory()
        {
            /*扩容步骤：
                创建一段新空间
                重新映射
                删除旧空间
            */
            int newsize = (_tables.size() == 0) ? 5 : 2 * _tables.size();
            HashTable<K, V> NewHT;
            NewHT._tables.resize(newsize);

            for (int i = 0; i < _tables.size(); i++)
            {
                if (_tables[i]._state == HashData<K, V>::EXIST)
                {
                    NewHT.insert(_tables[i]._kv);
                }
            }

            _tables.swap(NewHT._tables);
        }

    private:
        vector<HashData<K, V>> _tables;
        size_t _n = 0;

    public:
        static void Test1()
        {
            HashTable<int, int> hash;
            hash.insert({1, 1});
            hash.insert({12, 1});
            hash.insert({13, 1});
            hash.insert({16, 1});
            hash.insert({161, 1});
            hash.insert({162, 1});
            hash.insert({163, 1});
            hash.insert({164, 1});
            hash.insert({165, 1});
            hash.insert({16, 1});
            hash.insert({-16, 1});

            hash.Erase(16);
            hash.Erase(161);
            hash.Erase(162);
            hash.Erase(163);
            hash.insert({16, 1});
            hash.Erase(16);
            hash.insert({16, 1});

            hash.Order();
        }
    };

}

namespace HashBucket
{

    template <class T>
    class HashNode
    {
    public:
        HashNode(const T &data)
            : _data(data),
              _next(nullptr)
        {
        }

        HashNode<T> *_next;
        T _data;
    };

    template <class K, class T, class ExtractKey, class MyHash>
    class HashTable;

    template <class K, class T, class Ref, class Ptr, class ExtractKey, class MyHash>
    class __HTIterator
    {
    public:
        typedef HashTable<K, T, ExtractKey, MyHash> HT;
        typedef __HTIterator<K, T, Ref, Ptr, ExtractKey, MyHash> Self;
        typedef __HTIterator<K, T, T &, T *, ExtractKey, MyHash> Iterator;

        typedef HashNode<T> Node;

    public:
        __HTIterator(Node *node, const HT *ht)
            : _node(node), _ht(ht)
        {
        }

        __HTIterator(const Iterator &it)
            : _node(it._node), _ht(it._ht)
        {}

        Self &operator++()
        {
            /*如果当前桶没有遍历到结尾*/
            /*如果当前桶遍历到了结尾*/

            if (_node->_next != nullptr)
            {
                _node = _node->_next;
                return *this;
            }
            else
            {
                /*重新计算计算哈希值， 然后找到在哪一个桶*/
                ExtractKey tractKey;
                int hashi = tractKey(_node->_data) % _ht->_tables.size();
                /*从这个桶后面找一个新桶*/
                hashi++;
                while (hashi < _ht->_tables.size())
                {
                    Node *cur = _ht->_tables[hashi];
                    if (cur != nullptr)
                    {
                        _node = cur;
                        return *this;
                    }
                    hashi++;
                }
                _node = nullptr;
                return *this;
            }
        }

        Ref operator*()
        {
            return _node->_data;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }

        bool operator!=(const Self &it)
        {
            return _node != it._node;
        }

        bool operator==(const Self &it)
        {
            return _node == it._node;
        }

    public:
        Node *_node;
        const HT *_ht; /*保存一个指向自身的指针*/
    };

    template <class K, class T, class ExtractKey, class MyHash>
    class HashTable
    {
        template <class Key, class Value, class Ref, class Ptr, class extract_key, class my_hash>
        friend class  __HTIterator;

    public:
        typedef HashNode<T> Node;
        typedef HashBucket::HashTable<K, T, ExtractKey, MyHash> Self;
        typedef __HTIterator<K, T, T &, T *, ExtractKey, MyHash> Iterator;
        typedef __HTIterator<K, T, const T &, const T *, ExtractKey, MyHash> const_Iterator;

    public:
        // Iterator
        Iterator begin()
        {
            int hashi = 0;
            while (_tables[hashi] == nullptr)
                hashi++;
            return Iterator(_tables[hashi], this);
        }

        const_Iterator begin() const
        {
            int hashi = 0;
            while (_tables[hashi] == nullptr)
                hashi++;
            return const_Iterator(_tables[hashi], this);
        }

        Iterator end()
        {
            return Iterator(nullptr, this);
        }

        const_Iterator end() const
        {
            return const_Iterator(nullptr, this);
        }

        // Constructor
        ~HashTable()
        {
            for (int i = 0; i < _tables.size(); i++)
            {
                Node *cur = _tables[i];
                while (cur != nullptr)
                {
                    Node *next = cur->_next;
                    delete cur;
                    cur = next;
                }
            }
            _n = 0;
        }

        pair<Iterator, bool> Insert(const T &data)
        {
            if (_tables.size() == 0 || _n * 10 / _tables.size() == 10)
            {
                UpMemory();
            }
            if (Find(_tractKey(data)))
                return make_pair(end(), false);
            //
            int hashi = _hasher(_tractKey(data)) % _tables.size();
            Node *newnode = new Node(data);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            _n++;
            return make_pair(Iterator(newnode, this), true);
        }

        bool Erase(const K &key)
        {
            int hashi = _hasher(key) % _tables.size();
            Node *cur = _tables[hashi];
            if (_tractKey(cur->_data) == key)
            {
                _tables[hashi] = cur->_next;
                delete cur;
                return true;
            }
            Node *next = cur->_next;
            while (next != nullptr)
            {
                if (_tractKey(next->_data) == key)
                {
                    cur->_next = next->_next;
                    delete next;
                    return true;
                }
                cur = next;
                next = cur->_next;
            }
            return false;
        }

        Node *Find(const K &key)
        {
            int hashi = _hasher(key) % _tables.size();
            Node *cur = _tables[hashi];
            while (cur != nullptr)
            {
                if (_tractKey(cur->_data) == key)
                {
                    return cur;
                }
                cur = cur->_next;
            }
            return nullptr;
        }

        void Order()
        {
            for (int i = 0; i < _tables.size(); i++)
            {
                Node *cur = _tables[i];
                while (cur)
                {
                    cout << _tractKey(cur->_data) << endl;
                    cur = cur->_next;
                }
            }
        }

        void Some()
        {
            int BucketLen = 0;
            int maxBucketLen = 0;
            float SumLen = 0;
            int BucketCount = 0;

            for (int i = 0; i < _tables.size(); i++)
            {
                Node *cur = _tables[i];
                if (cur)
                    BucketCount++;

                BucketLen = 0;
                while (cur)
                {
                    BucketLen++;
                    cur = cur->_next;
                }

                SumLen += BucketLen;
                maxBucketLen = max(maxBucketLen, BucketLen);
            }

            cout << "BucketCount: " << BucketCount << endl;
            cout << "maxBucketLen: " << maxBucketLen << endl;
            cout << "AverageLen: " << SumLen / BucketCount << endl;
        }

    private:
        void UpMemory()
        {
            int newsize = (_tables.size() == 0) ? 5 : 2 * _tables.size();
            Self NewHT;
            NewHT._tables.resize(newsize);
            for (int i = 0; i < _tables.size(); i++)
            {
                Node *cur = _tables[i];
                while (cur)
                {
                    Node *next = cur->_next;
                    int hashi = _hasher(_tractKey(cur->_data)) % NewHT._tables.size();
                    cur->_next = NewHT._tables[hashi];
                    NewHT._tables[hashi] = cur;
                    cur = next;
                }
                /*这里不置为空， 那么这里_tables里面还保存着原本的节点的值， 一旦交换就会析构掉*/
                _tables[i] = nullptr;
            }
            _tables.swap(NewHT._tables);
        }

    private:
        vector<Node *> _tables;
        int _n;
        ExtractKey _tractKey;
        MyHash _hasher;

        // public:
        //     static void Test1()
        //     {
        //         HashTable<string, int> hash;
        //         hash.Insert({"1", 1});
        //         hash.Insert({"2", 1});
        //         hash.Insert({"13", 1});
        //         hash.Insert({"14", 1});
        //         hash.Insert({"15", 1});
        //         hash.Insert({"16", 1});
        //         hash.Insert({"161", 1});
        //         hash.Insert({"171", 1});
        //         hash.Insert({"181", 1});

        //         hash.Erase("171");
        //         hash.Erase("171");
        //         hash.Erase("181");
        //         hash.Erase("171");
        //         hash.Erase("171");
        //         hash.Erase("171");

        //         hash.Order();
        //         hash.Some();
        //     }
        //     static void Test2()
        //     {
        //         HashTable<string, int> hash;
        //         srand(time(nullptr) ^ 131);
        //         for (int i = 0; i < 10000; i++)
        //         {
        //             string tmp = to_string(rand());
        //             hash.Insert({tmp, 1});
        //         }

        //         hash.Some();
        //     }
    };
}

namespace MyHashFunc
{

    template <class K>
    struct MyHash
    {
        size_t operator()(const K &key)
        {
            return key;
        }
    };

    template <>
    struct MyHash<string>
    {
        size_t operator()(const string &key)
        {
            int hashi = 1;
            for (auto &e : key)
            {
                hashi *= 13;
                hashi += e;
            }

            return hashi & 0x7FFFFFFF;
        }
    };
}